package luo.hui.jiang.sort;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.locks.Condition;

/**
 * @author 罗惠江
 * @version 1.0
 * @email 1511619294@qq.com
 * @date 2020/7/31 9:34
 */
public class ShellSort {
    public static void main(String[] args) {
        int[] arr = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            arr[i] = (int) (Math.random() * 80000000);
        }

        long startTime = System.currentTimeMillis();
//        shellSort(arr);
        shellSort(arr);
        long endTime = System.currentTimeMillis();
        System.out.println("程序运行时间： " + (endTime - startTime) + "ms");
    }

    /**
     * 使用希尔排序算法 交换法
     */
    public static void shellSort(int[] arr) {
        int temp = 0;
        int count = 0;
        // 需要按不同的不具来进行排序  这里将我们原本的数组按不同的步长进行分组。 希尔排序的关键就是分组进行 增量排序
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            // 对 分组后的数据分别进行冒泡排序。
            for (int i = gap; i < arr.length; i++) {
                // 遍历各组中所有的元素（共 gap 组，每组有多少个元素），步长gap。
                for (int j = i - gap; j >= 0; j -= gap) {
                    if (arr[j] > arr[j + gap]) {
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
        }
    }


    /**
     * 使用希尔排序算法 移动法
     */
    public static void shellSort2(int[] arr) {
        int temp = 0;
        int index = 0;
        for (int garp = arr.length / 2; garp > 0; garp /= 2) {
            // 使用插入排序对分组内的数据进行排序
            for (int i = garp; i < arr.length; i++) {
                index = i;
                temp = arr[index];
                if (arr[index - garp] > arr[index]) {
                    while (index - garp >= 0 && arr[index - garp] > arr[index]) {
                        arr[index] = arr[index - garp];
                        index -= garp;
                    }
                    arr[index] = temp;
                }
            }
        }
    }
}
